package cn.edu.anan.algorithm.sort;

import java.util.Arrays;

/**
 * 快速排序算法：
 *  1.思想：
 *      1.1.分治思想，即假如有一个数组a[p...r]需要排序
 *      1.2.从待排序数组中选择一个元素pivot
 *      1.3.将数组中小于pivot的元素，放在pivot的左边
 *      1.4.将数组中大于pivot的元素，放在pivot的右边
 *      1.5.依次递归进行（1.2/1.3/1.4）
 *      1.6.直到p>=r终止。即完成数组的排序
 *  2.时间复杂度：
 *      通常情况是O(nlogn)，极端情况下会退化为O(n^2)
 *  3.空间复杂度：
 *      O(1)是原地排序算法
 *  4.是否是稳定排序算法：
 *      不是稳定排序算法
 */
public class QuickSort {

    /**
     * 快速排序入口
     * @param array  待排序数组
     * @param n     数据规模
     */
    public static void sort(Integer[] array,int n){
        // 如果数据规模小于等于1，不需要排序
        if(n <= 1){
            return;
        }

        // 快速排序
        quickSort(array,0,n-1);
    }

    /**
     * 快速排序（递归函数）
     * @param array
     * @param low
     * @param high
     */
    public static void quickSort(Integer[] array,int low,int high){
        // 终止条件
        if(low >= high){
            return;
        }

        // 分区函数寻找pivot
        int mid = partition(array,low,high);

        // 低位递归排序
        quickSort(array,low,mid-1);

        // 高位递归排序
        quickSort(array,mid+1,high);

    }

    /**
     * 分区函数
     * @param array
     * @param low
     * @param high
     * @return
     */
    public static int partition(Integer[] array,int low,int high){

        // 定义两个临时变量，方便输出数组（它们与排序无关）
        int tmpLow = low;
        int tmpHigh = high;

        // 选取第一个元素作为pivot（分区点）
        int pivot = array[low];

        System.out.println("2.1.本次分区：low="+low+"&high="+high+"，待排序序列："+printArray(array,tmpLow,tmpHigh)+",选择分区元素pivot：array["+low+"]="+pivot);

        // 循环处理low<high
        System.out.println("2.2.循环操作low<high：从右往左，将小于pivot的数据，放入左边.pivot="+pivot);
        System.out.println("2.3.循环操作low<high：从左往右，将大于pivot的数据，放入右边.pivot="+pivot);
        while (low<high){

            // 从右往左，将小于pivot的数据，放入左边
            while(low<high && array[high]>=pivot){
                high -=1;
            }
            array[low] = array[high];
            System.out.println("2.2.1.本次循环结束,low="+low+"&high="+high+",待排序序列："+printArray(array,tmpLow,tmpHigh));

            // 从左往右，将大于pivot的数据，放入右边
            while(low<high && array[low]<=pivot){
                low +=1;
            }
            array[high]=array[low];
            System.out.println("2.3.1.本次循环结束,low="+low+"&high="+high+",待排序序列："+printArray(array,tmpLow,tmpHigh));

        }

        // 找到分区点low，并返回
        array[low] = pivot;
        System.out.println("2.4.本次分区结束pivot：array["+low+"]="+pivot+"后,待排序序列："+printArray(array,tmpLow,tmpHigh));
        System.out.println("2.5.-------------------------华丽丽分割线-------------------------");
        return low;
    }

    /**
     * 根据数组起始位置，结束位置输出数组内容
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static String printArray(Integer [] array,int start,int end){
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        for(int i = start; i <= end;i++){
            builder.append(array[i]).append(",");
        }

        // 去掉最后一个：,
        String substring = builder.substring(0, builder.length() - 1);
        substring += "]";

        return substring;
    }
}
